package com.study.sort;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static com.study.sort.BubbleSort.exch;
import static com.study.sort.BubbleSort.greater;

// 希尔排序 插入排序的优化版，用增长量来分组
public class ShellSort
{
    int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};

    // // 2022版数据结构与算法
    @Test
    void sort1()
    {
        for (int gap = arr.length >> 1; gap > 0; gap = gap >> 1) {
            // low++ 不是一次把一个分组全部排完再排下一个分组，而是每一组排好一对然后排下一个分组的一对，如果 gap==1 时，就一次把这唯一的一组排完
            for (int low = gap; low < arr.length; low++) {
                // 将 low 位置的元素插入至 [0..low-1] 的已排序区域
                int t = arr[low];
                int i = low - gap; // 已排序区域指针
                while (i >= 0 && t < arr[i]) {  // 没有找到插入位置
                    arr[i + gap] = arr[i];      // 空出插入位置
                    i -= gap;
                }
                // 找到插入位置
                if (i != low - gap) {
                    arr[i + gap] = t;
                }
            }
        }
    }

    // // 2020版数据结构与算法
    @Test
    void sort()
    {
        //1.根据数组a的长度，确定增长量h的初始值；
        int h = 1;
        while (h < arr.length / 2) {
            h = 2 * h + 1;
        }
        while (h >= 1) {
            for (int i = h;     // 从增长量大小的索引位置开始，
                 i < arr.length; i++) {
                for (int j = i; j > 0; j -= h) {
                    if (greater(arr[j - h], arr[j])) {
                        exch(arr, j - h, j);
                    } else {
                        break;
                    }
                }
            }
            h /= 2;
        }
    }

    @BeforeEach
    void printArrBefore()
    {
        System.out.println(Arrays.toString(arr));
    }

    @AfterEach
    void printArrAfter()
    {
        System.out.println(Arrays.toString(arr));
    }
}
